<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.1.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.0.0/css/all.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/themes/green/pace-theme-minimal.css">
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/pace.min.js" integrity="sha256-gqd7YTjg/BtfqWSwsJOvndl0Bxc8gFImLEkXQT8+qj0=" crossorigin="anonymous"></script>

<script class="next-config" data-name="main" type="application/json">{"hostname":"liukairui.me","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.10.1","exturl":false,"sidebar":{"position":"left","display":"hide","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":true,"pangu":true,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null,"activeClass":"valine"},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="矩阵快速幂是使用矩阵乘法实现对于递推式的特大项实现快速求解，在乘法的时候又采用了快速幂，所以叫矩阵快速幂">
<meta property="og:type" content="article">
<meta property="og:title" content="数论-矩阵快速幂">
<meta property="og:url" content="http://liukairui.me/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/">
<meta property="og:site_name" content="LiuKairui Website">
<meta property="og:description" content="矩阵快速幂是使用矩阵乘法实现对于递推式的特大项实现快速求解，在乘法的时候又采用了快速幂，所以叫矩阵快速幂">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-10-30T16:00:05.000Z">
<meta property="article:modified_time" content="2021-10-18T06:44:13.576Z">
<meta property="article:author" content="Liu Kairui">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="笔记">
<meta property="article:tag" content="数论">
<meta property="article:tag" content="矩阵快速幂">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://liukairui.me/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://liukairui.me/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/","path":"article/数论-矩阵快速幂/","title":"数论-矩阵快速幂"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>数论-矩阵快速幂 | LiuKairui Website</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?ea07bceb8f5fa721da2ebf01833faa32"></script>



<div class="nindexBK">
<div class="nindexBKC"></div>
<div class="nindex">
  <h1>Hey👋</h1>
  <p style="font-weight: 500; font-size: 2.2em">欢迎访问Liu Kairui的个人站.</p>
  <p>
      我是一个来自重庆的在校大学生, 偏爱于前端技术<!--与OS设计-->, 偶尔使用 JS / Go 进行轻量项目开发, 欢迎访问我的
      <a href="https://github.com/KairuiLiu" target="_blank"><i class="fab fa-github-alt"></i> GitHub</a> .
  </p>
  <p>
      这个网站主要用来存储学习 / 瞎搞的笔记, 同时提供了邮件、图床等服务. 对于一些自认为有趣的<a href="javascript:;" id="myProj">项目</a>, 我也会将项目介绍, 文档, 甚至是设计指南发布在这里.
  </p>
  <ul>
    <li><p><a href="/artrank/" target="_blank">ArtRank</a>: 基于Node.JS的PageRank文献管理推荐系统</p></li>
    <li><p><a href="/gooj/" target="_blank">GoOJ</a>: 基于Golang的高校在线评测系统</p></li>
    <li><p><a href="/projects/" target="_blank">更多 <i class="fas fa-angle-right"></i></a></p></li>

  </ul>
  <p>
      可以在这些平台找到我: 
      <a href="https://www.zhihu.com/people/liu-kai-rui-18" target="_blank">知乎</a>,
      <a href="https://space.bilibili.com/33238144" target="_blank">bilibili</a>
      和
      <a href="https://www.coolapk.com/u/805314?from=qr" target="_blank">酷安</a>.
  </p>

  <p>
      下滑即可进入博客 <i class="fas fa-arrow-down"></i>
  </p>
</div>
</div>  

 
<script>
  var OriginTitile = document.title;
  var titleTime;
  document.addEventListener("visibilitychange", function() {
    if (document.hidden) {
      document.title = "谢谢离开 | " + OriginTitile;
      clearTimeout(titleTime);
    } else {
      document.title = "欢迎归来 | " + OriginTitile;
      titleTime = setTimeout(function() {
        document.title = OriginTitile;
      }, 2000);
    }
  });
</script>


<script>
  function checkIndex(){
    let nindexItems = [[".nindexBK","display","block","none"],[".headband","display","none","block"],["div.toggle.sidebar-toggle","visibility","hidden","visible"]]; // ,["button.darkmode-toggle","visibility","hidden","visible"]];
    let isIndex = new RegExp("^(\/){0,1}(index){0,1}(\.html){0,1}(/)*$").test(location.pathname);
    let backCanvas = document.querySelector(".nindexBK");
    nindexItems.dispShift = function (stat){this.forEach((e) => {try{document.querySelector(e[0]).style[e[1]]=e[2+stat];}catch{}})}
    if(isIndex){
      nindexItems.dispShift(0);
      window.onscroll=function(){
        if(document.documentElement.scrollTop>backCanvas.offsetHeight*1.05){
          nindexItems.dispShift(1);window.onscroll=null;
        }
      }
      document.querySelector("#myProj").onclick=()=>{
        let projlist = document.querySelector(".nindex>ul");
        projlist.className.indexOf("ulactive")==-1?projlist.classList.add("ulactive"):projlist.classList.remove("ulactive")
      }
    }else nindexItems.dispShift(1);
  }
  checkIndex();
</script>

<!--<script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>-->

  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<link rel="alternate" href="/atom.xml" title="LiuKairui Website" type="application/atom+xml">
<style>.darkmode--activated{--body-bg-color:#282828;--content-bg-color:#333;--card-bg-color:#555;--text-color:#ccc;--blockquote-color:#bbb;--link-color:#ccc;--link-hover-color:#eee;--brand-color:#ddd;--brand-hover-color:#ddd;--table-row-odd-bg-color:#282828;--table-row-hover-bg-color:#363636;--menu-item-bg-color:#555;--btn-default-bg:#222;--btn-default-color:#ccc;--btn-default-border-color:#555;--btn-default-hover-bg:#666;--btn-default-hover-color:#ccc;--btn-default-hover-border-color:#666;--highlight-background:#282b2e;--highlight-foreground:#a9b7c6;--highlight-gutter-background:#34393d;--highlight-gutter-foreground:#9ca9b6}.darkmode--activated img{opacity:.75}.darkmode--activated img:hover{opacity:.9}.darkmode--activated code{color:#69dbdc;background:0 0}button.darkmode-toggle{z-index:9999}.darkmode-ignore,img{display:flex!important}</style></head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">LiuKairui Website</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">要有信仰</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
        <li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
        <li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fas fa-hashtag fa-fw"></i>标签</a></li>
        <li class="menu-item menu-item-收藏夹"><a href="/favorites/" rel="section"><i class="fab fa-gratipay fa-fw"></i>收藏夹</a></li>
        <li class="menu-item menu-item-留言板"><a href="/messageBoard/" rel="section"><i class="fab fa-facebook-messenger fa-fw"></i>留言板</a></li>
        <li class="menu-item menu-item-项目"><a href="/projects/" rel="section"><i class="fa fa-satellite fa-fw"></i>项目</a></li>
        <li class="menu-item menu-item-图床"><a href="http://img.liukairui.me/" rel="noopener" target="_blank"><i class="fa fa-bed fa-fw"></i>图床</a></li>
        <li class="menu-item menu-item-云ide"><a href="http://vsc.liukairui.me/" rel="noopener" target="_blank"><i class="fas fa-code fa-fw"></i>云IDE</a></li>
        <li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li>
        <li class="menu-item menu-item-邮箱"><a href="http://mail.liukairui.me/mail" rel="noopener" target="_blank"><i class="fas fa-envelope-open-text fa-fw"></i>邮箱</a></li>
        <li class="menu-item menu-item-rss"><a href="/atom.xml" rel="section"><i class="fa fa-rss fa-fw"></i>RSS</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E4%B8%80%E9%81%93%E9%A2%98"><span class="nav-number">1.</span> <span class="nav-text">一道题：</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%9F%A9%E9%98%B5%E7%9A%84%E6%9E%84%E5%BB%BA%E4%B8%8E%E8%B5%8B%E5%80%BC"><span class="nav-number">1.1.</span> <span class="nav-text">矩阵的构建与赋值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%BE%93%E5%87%BA%E7%9F%A9%E9%98%B5%E8%B0%83%E8%AF%95%E7%94%A8%E6%9C%80%E5%90%8E%E5%81%9A%E9%A2%98%E7%9B%B4%E6%8E%A5%E8%AE%BF%E9%97%AE%E6%95%B0%E7%BB%84"><span class="nav-number">1.2.</span> <span class="nav-text">输出矩阵(调试用，最后做题直接访问数组)</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82%E7%9A%84%E5%BA%94%E7%94%A8"><span class="nav-number">2.</span> <span class="nav-text">矩阵快速幂的应用</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%9E%84%E9%80%A0%E6%96%B9%E6%B3%95"><span class="nav-number">3.</span> <span class="nav-text">构造方法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%95%B0%E5%88%97fnfn-1fn-21f1f21%E7%9A%84%E7%AC%ACn%E9%A1%B9%E7%9A%84%E5%BF%AB%E9%80%9F%E6%B1%82%E6%B3%95%E4%B8%8D%E8%80%83%E8%99%91%E9%AB%98%E7%B2%BE%E5%BA%A6"><span class="nav-number">3.0.0.1.</span> <span class="nav-text">1.
数列f[n]&#x3D;f[n-1]+f[n-2]+1,f[1]&#x3D;f[2]&#x3D;1的第n项的快速求法（不考虑高精度）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%95%B0%E5%88%97fnfn-1fn-2n1f1f21"><span class="nav-number">3.0.0.2.</span> <span class="nav-text">2.数列f[n]&#x3D;f[n-1]+f[n-2]+n+1,f[1]&#x3D;f[2]&#x3D;1</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%95%B0%E5%88%97fnfn-1fn-2f1f21%E7%9A%84%E5%89%8Dn%E9%A1%B9%E5%92%8Csnf1f2fn"><span class="nav-number">3.0.0.3.</span> <span class="nav-text">3.数列f[n]&#x3D;f[n-1]+f[n-2],f[1]&#x3D;f[2]&#x3D;1的前n项和s[n]&#x3D;f[1]+f[2]+……+f[n]</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%95%B0%E5%88%97fnfn-1fn-2n1f1f21%E7%9A%84%E5%89%8Dn%E9%A1%B9%E5%92%8Csnf1f2fn"><span class="nav-number">3.0.0.4.</span> <span class="nav-text">4.数列f[n]&#x3D;f[n-1]+f[n-2]+n+1,f[1]&#x3D;f[2]&#x3D;1的前n项和s[n]&#x3D;f[1]+f[2]+……+f[n]</span></a></li></ol></li></ol></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Liu Kairui"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">Liu Kairui</p>
  <div class="site-description" itemprop="description">LiuKairui Persional Website</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">45</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">24</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="https://github.com/KairuiLiu" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;KairuiLiu" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:tclkr@live.com" title="E-Mail → mailto:tclkr@live.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://qm.qq.com/cgi-bin/qm/qr?k=oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&noverify=0" title="QQ → https:&#x2F;&#x2F;qm.qq.com&#x2F;cgi-bin&#x2F;qm&#x2F;qr?k&#x3D;oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&amp;noverify&#x3D;0" rel="noopener" target="_blank"><i class="fab fa-qq fa-fw"></i>QQ</a>
      </span>
      <span class="links-of-author-item">
        <a href="/atom.xml" title="RSS → &#x2F;atom.xml"><i class="fa fa-rss fa-fw"></i>RSS</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://liukairui.blog.csdn.net/" title="CSDN → https:&#x2F;&#x2F;liukairui.blog.csdn.net" rel="noopener" target="_blank"><i class="fab fa-cuttlefish fa-fw"></i>CSDN</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://liukairui.cc/" title="国内站点 → http:&#x2F;&#x2F;liukairui.cc" rel="noopener" target="_blank"><i class="fa fa-globe fa-fw"></i>国内站点</a>
      </span>
  </div>
  <div class="cc-license site-overview-item animated" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" class="cc-opacity" rel="noopener" target="_blank"><img src="https://cdnjs.cloudflare.com/ajax/libs/creativecommons-vocabulary/2020.11.3/assets/license_badges/small/by_nc_sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll site-overview-item animated">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://paste.ubuntu.com/" title="https:&#x2F;&#x2F;paste.ubuntu.com&#x2F;" rel="noopener" target="_blank">Ubuntu Pastebin</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://send.firefox.com/" title="https:&#x2F;&#x2F;send.firefox.com&#x2F;" rel="noopener" target="_blank">Firefox Send</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://jkwzs.cn/" title="https:&#x2F;&#x2F;jkwzs.cn&#x2F;" rel="noopener" target="_blank">南花醉笔丶の个人博客</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://ywrby.cn/" title="https:&#x2F;&#x2F;ywrby.cn&#x2F;" rel="noopener" target="_blank">Ywrby个人博客</a>
        </li>
    </ul>
  </div>

        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://liukairui.me/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="Liu Kairui">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LiuKairui Website">
      <meta itemprop="description" content="LiuKairui Persional Website">
    </span>
    
    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="数论-矩阵快速幂 | LiuKairui Website">
      <meta itemprop="description" content="矩阵快速幂是使用矩阵乘法实现对于递推式的特大项实现快速求解，在乘法的时候又采用了快速幂，所以叫矩阵快速幂">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          数论-矩阵快速幂
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-10-31 00:00:05" itemprop="dateCreated datePublished" datetime="2020-10-31T00:00:05+08:00">2020-10-31</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/%E7%AC%94%E8%AE%B0/" itemprop="url" rel="index"><span itemprop="name">笔记</span></a>
        </span>
    </span>

  
    <span id="/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/" class="post-meta-item leancloud_visitors" data-flag-title="数论-矩阵快速幂" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">Valine：</span>
  
    <a title="valine" href="/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

<script>
    CONFIG.hostname = location.hostname;
</script>
    <span class="post-meta-break"></span>
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>6.5k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>6 分钟</span>
    </span>
</div>

            <div class="post-description">矩阵快速幂是使用矩阵乘法实现对于递推式的特大项实现快速求解，在乘法的时候又采用了快速幂，所以叫矩阵快速幂</div>
        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h1 id="一道题">一道题：</h1>
<p>求斐波那契的第i项对<span
class="math inline">\(10^9+7\)</span>求余的值（i&lt;<span
class="math inline">\(10^{10}\)</span>）</p>
<ul>
<li>算法一： 递推，会TLE</li>
<li>算法二： 你偷偷百度了一下 找到了fib的通项公式 <span
class="math display">\[fib(n)=\frac {1}{\sqrt5}
\left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right]\]</span>
但是这个无法求余，并且数字超过了double的有效位数</li>
</ul>
<p>这时候只能使用矩阵快速了 考虑如下 <span
class="math display">\[\begin{bmatrix}
    1 &amp; 1\\
    1 &amp;0 \\
\end{bmatrix}
*
\begin{bmatrix}
1\\
1\\
\end{bmatrix}=
\begin{bmatrix}
2\\
1\\
\end{bmatrix}
\]</span> 也就是 <span class="math display">\[\begin{bmatrix}
    1 &amp; 1\\
    1 &amp;0 \\
\end{bmatrix}
*
\begin{bmatrix}
fib(2)\\
fib(1)\\
\end{bmatrix}=
\begin{bmatrix}
fib(1)+fib(2)\\
0+fib(2)\\
\end{bmatrix}=
\begin{bmatrix}
fib(3)\\
fib(2)
\end{bmatrix}
\]</span> 我们继续往下写 <span class="math display">\[\begin{bmatrix}
    1 &amp; 1\\
    1 &amp; 0\\
\end{bmatrix}
*
\begin{bmatrix}
2\\
1\\
\end{bmatrix}=
\begin{bmatrix}
3\\
2\\
\end{bmatrix}
\]</span> 也就是 <span class="math display">\[\begin{bmatrix}
    1 &amp; 1\\
    1 &amp;0\\
\end{bmatrix}
*
\begin{bmatrix}
fib(3)\\
fib(2)\\
\end{bmatrix}=
\begin{bmatrix}
fib(2)+fib(3)\\
0+fib(3)\\
\end{bmatrix}=
\begin{bmatrix}
fib(4)\\
fib(3)
\end{bmatrix}
\]</span></p>
<p>于是我们得出结论</p>
<p><span class="math display">\[
\begin{bmatrix}
1&amp;1\\
1&amp;0\\
\end{bmatrix}^n*
\begin{bmatrix}
1\\
1
\end{bmatrix}=
\begin{bmatrix}
fib(n+2)\\
fib(n+1)
\end{bmatrix}
\]</span></p>
<p>至此，最难解决的问题就是如何进行矩阵相乘了
有一个<code>n次方</code>我想到使用快速幂可以求解
所以我们先要解决<code>矩阵乘法*</code></p>
<h2 id="矩阵的构建与赋值">矩阵的构建与赋值</h2>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token comment">//构建矩阵结构体</span>
<span class="token keyword">struct</span> <span class="token class-name">maix</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> n<span class="token punctuation">,</span>m<span class="token punctuation">;</span>
    <span class="token keyword">int</span> mat<span class="token punctuation">[</span><span class="token number">50</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">50</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
<span class="token comment">//使用这种方法赋值 数字会按结构体定义顺序赋值n,m,mat,尤其注意数组赋值</span>
maix a<span class="token operator">=</span><span class="token punctuation">&#123;</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>	
maix b<span class="token operator">=</span><span class="token punctuation">&#123;</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span></code></pre>
<p>a矩阵为(从下标1开始) <span class="math display">\[
\begin{bmatrix}
1&amp;1\\
1&amp;0\\
\end{bmatrix}
\]</span> ## 矩阵乘法</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token comment">//乘法</span>
maix <span class="token function">mul</span><span class="token punctuation">(</span>maix x<span class="token punctuation">,</span>maix y<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    maix res<span class="token punctuation">;</span>res<span class="token punctuation">.</span>n<span class="token operator">=</span>x<span class="token punctuation">.</span>n<span class="token punctuation">;</span>res<span class="token punctuation">.</span>m<span class="token operator">=</span>y<span class="token punctuation">.</span>m<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>x<span class="token punctuation">.</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>k<span class="token operator">&lt;=</span>y<span class="token punctuation">.</span>m<span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            res<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>y<span class="token punctuation">.</span>n<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
                res<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">+=</span>x<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">*</span>y<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>然后就是快速幂了 1. 错误示范：
我只想求前面这个矩阵的n次方，于是写了函数</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">maix <span class="token function">matrix_pow</span><span class="token punctuation">(</span>maix x<span class="token punctuation">,</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    maix res<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span>y<span class="token operator">=</span><span class="token function">mul</span><span class="token punctuation">(</span>res<span class="token punctuation">,</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        x<span class="token operator">=</span><span class="token function">mul</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        n<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> y<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>有一个问题，就是我们在普通快速幂中可以做一个res用来放结果，因为我们可以随意创建一个数值1，但是在这里，我们<strong>无法创建一个同大小的单位矩阵</strong>
所以这里的解决办法是把后面那个 <span class="math display">\[
\begin{bmatrix}
fib(2)\\
fib(1)
\end{bmatrix}
\]</span> 作为res，顺便也处理掉，于是我们写下正确代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">maix <span class="token function">maix_pow</span><span class="token punctuation">(</span>maix x<span class="token punctuation">,</span>maix y<span class="token punctuation">,</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span>y<span class="token operator">=</span><span class="token function">mul</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>y<span class="token punctuation">)</span><span class="token punctuation">;</span>	<span class="token comment">//矩阵乘法左右千万别错</span>
        x<span class="token operator">=</span><span class="token function">mul</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        n<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> y<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h2
id="输出矩阵调试用最后做题直接访问数组">输出矩阵(调试用，最后做题直接访问数组)</h2>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">void</span> <span class="token function">print_maix</span><span class="token punctuation">(</span>maix res<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"PR n="</span><span class="token operator">&lt;&lt;</span>res<span class="token punctuation">.</span>n<span class="token operator">&lt;&lt;</span><span class="token string">" "</span><span class="token operator">&lt;&lt;</span>res<span class="token punctuation">.</span>m<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span> 
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>res<span class="token punctuation">.</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>res<span class="token punctuation">.</span>m<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
            cout<span class="token operator">&lt;&lt;</span>res<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span><span class="token string">" "</span><span class="token punctuation">;</span>
        cout<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"=======================\n"</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>完整的代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">struct</span> <span class="token class-name">maix</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> n<span class="token punctuation">,</span>m<span class="token punctuation">;</span>
    <span class="token keyword">int</span> mat<span class="token punctuation">[</span><span class="token number">50</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">50</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">print_maix</span><span class="token punctuation">(</span>maix res<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"PR n="</span><span class="token operator">&lt;&lt;</span>res<span class="token punctuation">.</span>n<span class="token operator">&lt;&lt;</span><span class="token string">" "</span><span class="token operator">&lt;&lt;</span>res<span class="token punctuation">.</span>m<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span> 
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>res<span class="token punctuation">.</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>res<span class="token punctuation">.</span>m<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
            cout<span class="token operator">&lt;&lt;</span>res<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span><span class="token string">" "</span><span class="token punctuation">;</span>
        cout<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token string">"=======================\n"</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

maix <span class="token function">mul</span><span class="token punctuation">(</span>maix x<span class="token punctuation">,</span>maix y<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    maix res<span class="token punctuation">;</span>res<span class="token punctuation">.</span>n<span class="token operator">=</span>x<span class="token punctuation">.</span>n<span class="token punctuation">;</span>res<span class="token punctuation">.</span>m<span class="token operator">=</span>y<span class="token punctuation">.</span>m<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>x<span class="token punctuation">.</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>k<span class="token operator">&lt;=</span>y<span class="token punctuation">.</span>m<span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            res<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>y<span class="token punctuation">.</span>n<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
                res<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">+=</span>x<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">*</span>y<span class="token punctuation">.</span>mat<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

maix <span class="token function">maix_pow</span><span class="token punctuation">(</span>maix x<span class="token punctuation">,</span>maix y<span class="token punctuation">,</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span>y<span class="token operator">=</span><span class="token function">mul</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>y<span class="token punctuation">)</span><span class="token punctuation">;</span>
        x<span class="token operator">=</span><span class="token function">mul</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        n<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> y<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    maix a<span class="token operator">=</span><span class="token punctuation">&#123;</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
    maix b<span class="token operator">=</span><span class="token punctuation">&#123;</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#123;</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">&#125;</span><span class="token punctuation">,</span><span class="token punctuation">&#123;</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
    <span class="token function">print_maix</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">print_maix</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">print_maix</span><span class="token punctuation">(</span><span class="token function">maix_pow</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b<span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<h1 id="矩阵快速幂的应用">矩阵快速幂的应用</h1>
<p>常用于求递推数列</p>
<h1 id="构造方法">构造方法</h1>
<p>一般的我们会通过递推式构造矩阵，一般多项式有几项我们构造几乘几的矩阵(包括常数)</p>
<h4 id="数列fnfn-1fn-21f1f21的第n项的快速求法不考虑高精度">1.
数列f[n]=f[n-1]+f[n-2]+1,f[1]=f[2]=1的第n项的快速求法（不考虑高精度）</h4>
<p>考虑3x1的矩阵 <span class="math display">\[
\begin{bmatrix}
f(n-2)\\
f(n-1)\\
1
\end{bmatrix}
\]</span> ，希望求得某3×3的矩阵A，使得此1×3的矩阵乘以A得到矩阵: <span
class="math display">\[
\begin{bmatrix}
f(n-1)\\
f(n)\\
1
\end{bmatrix}
\]</span> 即： <span class="math display">\[
A*\begin{bmatrix}
f(n-2)\\
f(n-1)\\
1
\end{bmatrix}=
\begin{bmatrix}
f(n-1)\\
f(n)\\
1
\end{bmatrix}
\]</span> 构造矩阵 <span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0\\
1&amp;1&amp;1\\
0&amp;0&amp;1\\
\end{bmatrix}
\]</span> 故： <span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0\\
1&amp;1&amp;1\\
0&amp;0&amp;1\\
\end{bmatrix}^n*
\begin{bmatrix}
f(n-2)\\
f(n-1)\\
1
\end{bmatrix}=
\begin{bmatrix}
f(n-1)\\
f(n)\\
1
\end{bmatrix}
\]</span></p>
<h4
id="数列fnfn-1fn-2n1f1f21">2.数列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1</h4>
<p>考虑4x1的矩阵 <span class="math display">\[
\begin{bmatrix}
f(n-2)\\
f(n-1)\\
n\\
1
\end{bmatrix}
\]</span> 希望求得某4×4的矩阵A，使得Ac乘以此矩阵得到矩阵： <span
class="math display">\[
\begin{bmatrix}
f(n-1)\\
f(n)\\
n\\
1
\end{bmatrix}
\]</span> 即： <span class="math display">\[
A*\begin{bmatrix}
f(n-2)\\
f(n-1)\\
n\\
1
\end{bmatrix}=
\begin{bmatrix}
f(n-1)\\
f(n-1)+f(n-2)\\
n+1\\
1
\end{bmatrix}
\]</span> 容易构造出这个4×4的矩阵A，即： <span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0&amp;0\\
1&amp;1&amp;1&amp;1\\
0&amp; 0&amp;1&amp;1\\
0&amp;0&amp;0&amp;1\\
\end{bmatrix}
\]</span> 故： <span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0&amp;0\\
1&amp;1&amp;1&amp;1\\
0&amp; 0&amp;1&amp;1\\
0&amp;0&amp;0&amp;1\\
\end{bmatrix}^n*\begin{bmatrix}
f(n-2)\\
f(n-1)\\
n\\
1
\end{bmatrix}=
\begin{bmatrix}
f(n-1)\\
f(n-1)+f(n-2)\\
n+1\\
1
\end{bmatrix}
\]</span></p>
<h4
id="数列fnfn-1fn-2f1f21的前n项和snf1f2fn">3.数列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的前n项和s[n]=f[1]+f[2]+……+f[n]</h4>
<p>仿照之前的思路，考虑3x1的矩阵 <span class="math display">\[
\begin{bmatrix}
f(n-2)\\
f(n-1)\\
s(n-2)
\end{bmatrix}
\]</span> ，我们希望通过乘以一个3×3的矩阵A，得到1×3的矩阵: <span
class="math display">\[
\begin{bmatrix}
f(n-1)\\
f(n)\\
s(n-1)
\end{bmatrix}
\]</span> 即： <span class="math display">\[
A*
\begin{bmatrix}
f(n-2)\\
f(n-1)\\
s(n-2)
\end{bmatrix}=
\begin{bmatrix}
f(n-1)\\
f(n)\\
s(n-1)
\end{bmatrix}
\]</span> 容易得到这个3×3的矩阵A是： <span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0\\
0&amp;1&amp;0\\
0&amp;1&amp;1\\
\end{bmatrix}
\]</span> 这种方法的矩阵规模是<span
class="math inline">\((r+1)^2\)</span> <span
class="math inline">\(f(1)=f(2)=s(1)=1\)</span>，所以，有 <span
class="math display">\[
\begin{bmatrix}
f(1)\\
f(2)\\
s(1)
\end{bmatrix}=
\begin{bmatrix}
f(2)\\
f(3)\\
s(2)
\end{bmatrix}
\]</span> 故： <span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0\\
0&amp;1&amp;0\\
0&amp;1&amp;1\\
\end{bmatrix}^{n-1}*
\begin{bmatrix}
f(1)\\
f(2)\\
s(1)
\end{bmatrix}=
\begin{bmatrix}
f(2)\\
f(3)\\
s(2)
\end{bmatrix}
\]</span></p>
<h4
id="数列fnfn-1fn-2n1f1f21的前n项和snf1f2fn">4.数列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1的前n项和s[n]=f[1]+f[2]+……+f[n]</h4>
<p>考虑5×1的矩阵 <span class="math display">\[
\begin{bmatrix}
f(n-2)\\
f(n-1)\\
s(n-2)\\
n\\
1
\end{bmatrix}
\]</span> 我们需要找到一个5×5的矩阵A，使得它乘以A得到如下1×5的矩阵 <span
class="math display">\[
\begin{bmatrix}
f(n-1)\\
f(n)\\
s(n-1)\\
n+1\\
1
\end{bmatrix}
\]</span> 即：【f[n-2],f[n-1],s[n-2],n,1】* A
=【f[n-1],f[n],s[n-1],n+1,1】</p>
<p>=【f[n-1], f[n-1]+f[n-2]+n+1,s[n-2]+f[n-1],n+1,1】 容易构造出A为：
<span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0&amp;0&amp;0\\
1&amp;1&amp;1&amp;0&amp;0\\
0&amp;1&amp;1&amp;0&amp;0\\
0&amp;0&amp;0&amp;1&amp;1\\
0&amp;0&amp;0&amp;0&amp;1\\
\end{bmatrix}
\]</span> 故：【f(1),f(2),s(1),3,1】* A^(n-1) =
【f(n),f(n+1),s(n),n+2,1】 <span class="math display">\[
\begin{bmatrix}
0&amp;1&amp;0&amp;0&amp;0\\
1&amp;1&amp;1&amp;0&amp;0\\
0&amp;1&amp;1&amp;0&amp;0\\
0&amp;0&amp;0&amp;1&amp;1\\
0&amp;0&amp;0&amp;0&amp;1\\
\end{bmatrix}^{n-1}*
\begin{bmatrix}
f(1)\\
f(2)\\
f(1)\\
f(3)\\
1
\end{bmatrix}=
\begin{bmatrix}
f(n)\\
f(n+1)\\
s(n)\\
n+2\\
1
\end{bmatrix}
\]</span> 一般地，如果有<span
class="math inline">\(f[n]=p*f(n-1)+q*f(n-2)+r*n+s\)</span>
可以构造矩阵A为： <span class="math display">\[
\begin{bmatrix}
0&amp;q&amp;0&amp;0&amp;0\\
1&amp;p&amp;1&amp;0&amp;0\\
0&amp;0&amp;1&amp;0&amp;0\\
0&amp;r&amp;0&amp;1&amp;0\\
0&amp;s&amp;0&amp;1&amp;1\\
\end{bmatrix}
\]</span> 更一般的，对于<span
class="math inline">\(f[n]=\Sigma(a[n-i]*f[n-i])+Poly(n)\)</span>，其中<span
class="math inline">\(0&lt;i\leq某常数c\)</span>, <span
class="math inline">\(Poly
(n)\)</span>表示n的多项式，我们依然可以构造类似的矩阵<span
class="math inline">\(A\)</span>来解决问题。 设<span
class="math inline">\(Degree(Poly(n))=d,\)</span> 并规定<span
class="math inline">\(Poly(n)=0\)</span>时，<span
class="math inline">\(d=-1\)</span>，此时对应于常系数线性齐次递推关系。则本方法求前n项和的复杂度为：
<span class="math display">\[O((c+1)+(d+1))3*log(n)\]</span></p>

    </div>

    
    
    
      


    <footer class="post-footer">
          <div class="reward-container">
  <div></div>
  <button>
    赞赏
  </button>
  <div class="post-reward">
      <div>
        <img src="/images/wechatpay.png" alt="Liu Kairui 微信">
        <span>微信</span>
      </div>
      <div>
        <img src="/images/alipay.png" alt="Liu Kairui 支付宝">
        <span>支付宝</span>
      </div>

  </div>
</div>

          

<div class="post-copyright">
<ul>
  <li class="post-copyright-author">
      <strong>本文作者： </strong>Liu Kairui
  </li>
  <li class="post-copyright-link">
      <strong>本文链接：</strong>
      <a href="http://liukairui.me/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/" title="数论-矩阵快速幂">http://liukairui.me/article/数论-矩阵快速幂/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

          <div class="post-tags">
              <a href="/tags/%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 算法</a>
              <a href="/tags/%E7%AC%94%E8%AE%B0/" rel="tag"><i class="fa fa-tag"></i> 笔记</a>
              <a href="/tags/%E6%95%B0%E8%AE%BA/" rel="tag"><i class="fa fa-tag"></i> 数论</a>
              <a href="/tags/%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/" rel="tag"><i class="fa fa-tag"></i> 矩阵快速幂</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/article/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95-%E5%88%A4%E6%96%AD%E4%B8%A4%E7%BA%BF%E6%AE%B5%E6%98%AF%E5%90%A6%E7%9B%B8%E4%BA%A4/" rel="prev" title="计算几何-判断两线段是否相交">
                  <i class="fa fa-chevron-left"></i> 计算几何-判断两线段是否相交
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/article/%E6%95%B0%E8%AE%BA-%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97%E7%9A%84%E5%A5%87%E6%80%AA%E6%80%A7%E8%B4%A8/" rel="next" title="数论-斐波那契数列的奇怪性质">
                  数论-斐波那契数列的奇怪性质 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments" id="valine-comments"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 2019 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Liu Kairui</span>
</div>
<div class="busuanzi-count">
    <span class="post-meta-item" id="busuanzi_container_site_uv">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-item" id="busuanzi_container_site_pv">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>
  <div class="addthis_inline_share_toolbox">
    <script src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-6231eb6f709fc868" async="async"></script>
  </div><script
  async
  src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"
></script>

 
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/moment.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment-precise-range-plugin@1.3.0/moment-precise-range.min.js"></script>
<script>
  function timer() {
    var ages = moment.preciseDiff(moment(),moment(20201101,"YYYYMMDD"));
    ages = ages.replace(/years?/, "年");
    ages = ages.replace(/months?/, "月");
    ages = ages.replace(/days?/, "天");
    ages = ages.replace(/hours?/, "小时");
    ages = ages.replace(/minutes?/, "分");
    ages = ages.replace(/seconds?/, "秒");
    ages = ages.replace(/\d+/g, '<span class="daysCnt" style="color:#1890ff">$&</span>');
    div.innerHTML = `我已在此等候你 ${ages}`;
    div.className="workDays";
  }
  var div = document.createElement("div");
  //插入到copyright之后
  var copyright = document.querySelector(".copyright");
  document.querySelector(".footer-inner").insertBefore(div, copyright.nextSibling);
  timer();
  setInterval("timer()",1000)
</script>



    </div>
  </footer>

  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/@next-theme/pjax@0.5.0/pjax.min.js" integrity="sha256-3NkoLDrmHLTYj7csHIZSr0MHAFTXth7Ua/DDt4MRUAg=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.js" integrity="sha256-yt2kYMy0w8AbtF89WXb2P1rfjcP/HTHLT7097U8Y5b8=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/lozad.js/1.16.0/lozad.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pangu/4.0.7/pangu.min.js"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  
<script src="https://cdn.jsdelivr.net/npm/hexo-generator-searchdb@1.4.0/dist/search.js" integrity="sha256-vXZMYLEqsROAXkEw93GGIvaB2ab+QW6w3+1ahD9nXXA=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>


  <script class="next-config" data-name="mermaid" type="application/json">{"enable":true,"theme":"forest","js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mermaid/8.14.0/mermaid.min.js","integrity":"sha256-7wT34TI0pEBeEFoi4z+vhuSddGh6vUTMWdqJ2SDe2jg="}}</script>
  <script src="/js/third-party/tags/mermaid.js"></script>

  <script src="/js/third-party/fancybox.js"></script>

  <script src="/js/third-party/pace.js"></script>

  
  <script data-pjax async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>


  <script class="next-config" data-name="leancloud_visitors" type="application/json">{"enable":true,"app_id":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","app_key":"xxGXdTTEGEVifs2TLB35844I","server_url":"https://abklvts4.lc-cn-e1-shared.com","security":false}</script>
  <script src="/js/third-party/statistics/lean-analytics.js"></script>


  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","mhchem":true,"js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.0/es5/tex-mml-chtml.min.js"}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


  <script src="https://cdnjs.cloudflare.com/ajax/libs/quicklink/2.2.0/quicklink.umd.js" integrity="sha256-4kQf9z5ntdQrzsBC3YSHnEz02Z9C1UeW/E9OgnvlzSY=" crossorigin="anonymous"></script>
  <script class="next-config" data-name="quicklink" type="application/json">{"enable":true,"home":false,"archive":false,"delay":true,"timeout":3000,"priority":true,"url":"http://liukairui.me/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/"}</script>
  <script src="/js/third-party/quicklink.js"></script>
<script src="https://cdn.jsdelivr.net/npm/darkmode-js@1.5.7/lib/darkmode-js.min.js"></script>

<script>
var options = {
  bottom: '64px',
  right: 'unset',
  left: '32px',
  time: '0.5s',
  mixColor: 'transparent',
  backgroundColor: 'transparent',
  buttonColorDark: '#100f2c',
  buttonColorLight: '#fff',
  saveInCookies: true,
  label: '🌓',
  autoMatchOsTheme: true
}
const darkmode = new Darkmode(options);
window.darkmode = darkmode;
darkmode.showWidget();
</script>


<script class="next-config" data-name="valine" type="application/json">{"enable":true,"appId":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","appKey":"xxGXdTTEGEVifs2TLB35844I","serverURLs":"https://abklvts4.lc-cn-e1-shared.com","placeholder":"请开始你的表演","avatar":"identicon","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-CN","visitor":false,"comment_count":true,"recordIP":true,"enableQQ":true,"requiredFields":[],"el":"#valine-comments","path":"/article/%E6%95%B0%E8%AE%BA-%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/"}</script>
<script>
document.addEventListener('page:loaded', () => {
  NexT.utils.loadComments(CONFIG.valine.el)
    .then(() => NexT.utils.getScript(
      'https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js',
      { condition: window.Valine }
    ))
    .then(() => {
      new Valine(CONFIG.valine);
    });
});
</script>


  <script async src="/js/fireworks.js"></script>




  <script src="/js/activate-power-mode.min.js"></script>
  <script>
    POWERMODE.colorful = true;
    POWERMODE.shake = false;
    document.body.addEventListener('input', POWERMODE);
  </script>




  <script src="/js/wobblewindow.js"></script>
  <script>
    //只在桌面版网页启用特效 记得同步到header.njk
    if( window.innerWidth > 768  ){
      $(document).ready(function () {
        
          $('body>main>header').wobbleWindow({
            radius: 50,
            movementTop: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        

        //
        //  $('body header>aside').wobbleWindow({
        //    radius: 50,
        //    movementLeft: false,
        //    movementTop: false,
        //    movementBottom: false,
        //    position: 'fixed',
        //    debug: false,
        //  });
        //

        
          $('body>footer').wobbleWindow({
            radius: 50,
            movementBottom: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        
      });
    }
  </script>


 
<script>
  $(document).ready(function(){
    var beian = document.querySelector(".footer-inner > .beian > a");
    var cpr=document.querySelector(".footer-inner > .copyright");
    var cnz=document.querySelector(".workDays");//.parentNode;
    var bsz=document.querySelector(".busuanzi-count");
    if(cnz!=null&&bsz!=null)
      cnz.parentNode.insertBefore(bsz,cnz);
    if(bsz == null || bsz == undefined || document.querySelector("#busuanzi_value_site_pv").innerText=="" || document.querySelector("#busuanzi_value_site_uv").innerText == "")
      bsz.remove();
    checkIndex();
    if(beian){cpr.classList.add('split-line');cpr.appendChild(beian);}
  })
  $(document).on('pjax:complete',checkIndex);
</script>



<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"log":false,"model":{"jsonPath":"/live2dw/assets/hijiki.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"react":{"opacity":0.7}});</script></body>
</html>
